package com.elloe.数组.二分查找;

/**
 * @author ElloeStudy(Sifa Zhang)
 * @create 2022-03-10 21:10
 * To: 真常应物，真常得性，常清常静，常清静矣
 */
public class SearchRange {
    int[] searchRanges(int[] nums,int target){
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一： target 在数组的范围右边或者左边
        if (leftBorder == -2 || rightBorder == -2) {
            return new int[]{-1,-1};
        }
        // 情况三： target 在数组的范围里面，且在数组的里面
        if (rightBorder-leftBorder > 1) {
            return new int[]{leftBorder+1,rightBorder-1};
        }
        // 情况二： target 在数组的范围里面，但是不在数组的元素里面1
        return new int[]{-1,1};
    }

    int getRightBorder(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 计入一下rightBorder没有被赋值
        while (left<= right){
            int middle = left + ((right-left)/2);
            if (nums[middle]>target){
                right = middle - 1;
            }else {
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    int getLeftBorder(int[] nums ,int target){
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 计入一下 左边界没有被赋值的情况
        while (left<=right){
            int middle = left + ((right - left)/2);
            if (nums[middle]>=target){
                right = middle - 1;
                leftBorder = right;
            }else{
                left = middle +1;
            }
        }
        return leftBorder;
    }
}

// 第二种解法
class Solution2{
    public static void main(String[] args) {
        int[] nums ={5,7,7,8,8,10};
        int target = 6;
        int[] ints = new Solution2().searchRange(nums, target);
        for (int x : ints ) {
            System.out.println(x);
        }
    }

    public void s1(){
        // 不是static 方法可以直接调用同一个类里面的其他方法
        // static方法需要 new 对象点方法获取
        int[] nums ={5,7,7,8,8,10};
        int target = 6;
        searchRange(nums, target);
    }

    public int[] searchRange(int[] nums,int target){
        int index = binarySearch(nums, target);

        if (index==-1){   // nums 里面不存在 target ,直接返回{-1,1}
            return new int[]{-1,-1};
        }
        // nums 中存在 target , 则左右滑动指针，来寻找符合条件的区间
        int left = index;
        int right = index;
        // 向左滑动，寻找左边界
        while (left-1 >= 0 && nums[left-1]==nums[index]){
            left -- ;
        }
        // 向右滑动，寻找右边界
        while (right+1 < nums.length && nums[right+1]==nums[index]){
            right++;
        }
        return new int[]{left,right};
    }

    public int binarySearch(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;   // 不变量 ， 查找target是否在这个区间里面

        while (left <= right){
            int mid = left + ((right - left)/2);
            if (nums[mid]==target){
                return mid;
            }else if (nums[mid]<target){
                left = mid + 1;
            }else{
                right = mid - 1 ;
            }
        }
        return -1;  // 查找的target不存在数组元素的区间里面
    }
}
